package com.cuz.hot100;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Q77combine {
    public static void main(String[] args) {
        System.out.println(combine1(4, 2));
        System.out.println(combine2(4, 2));
    }

    public static List<List<Integer>> combine1(int n, int k) {
        if (k <= 0 || k > n) {
            return Collections.emptyList();
        }
        int[] canUseNum = new int[n];
        for (int i = 0; i < n; i++) {
            canUseNum[i] = i + 1;
        }
        List<List<Integer>> res = new LinkedList<>();
        process(res, new LinkedList<>(), 0, k, canUseNum);
        return res;
    }


    private static void process(List<List<Integer>> res, LinkedList<Integer> tempRes,
                                int curUseCount, int k, int[] canUseNum) {
        if (curUseCount == k) {
            res.add(new ArrayList<>(tempRes));
            return;
        }
        for (int index = 0; index < canUseNum.length; index++) {
            if (canUseNum[index] > 0 && (tempRes.size() == 0 || canUseNum[index] > tempRes.getLast())) {
                int curUse = canUseNum[index];
                canUseNum[index] = -canUseNum[index];
                tempRes.addLast(curUse);
                process(res, tempRes, curUseCount + 1, k, canUseNum);
                tempRes.removeLast();
                canUseNum[index] = -canUseNum[index];
            }
        }
    }


    public static List<List<Integer>> combine2(int n, int k) {
        if (k <= 0 || k > n) {
            return Collections.emptyList();
        }

        List<List<Integer>> res = new LinkedList<>();
        process2(res, new LinkedList<>(), k, n, 1);
        return res;
    }
    private static void process2(List<List<Integer>> res, LinkedList<Integer> tempRes,
                                 int k, int n, int cur) {
        //比如 n =4  k=2 我们选择4开头这时候 4-4+1<2 因为 4开头不可以构造出答案
        if (tempRes.size() + n - cur + 1 < k) {
            return;
        }
        if (tempRes.size() == k) {
            res.add(new ArrayList<>(tempRes));
            return;
        }
        tempRes.addLast(cur);
        process2(res, tempRes, k, n, cur + 1);
        tempRes.removeLast();
        process2(res, tempRes, k, n, cur + 1);
    }
}
